home *** CD-ROM | disk | FTP | other *** search
/ X User Tools / X User Tools (O'Reilly and Associates)(1994).ISO / sun4c / archive / tcltk.z / tcltk / man / cat3 / Hash.3 < prev    next >
Text File  |  1994-09-20  |  12KB  |  331 lines
  1.  
  2.  
  3.  
  4. Tcl_Hash(3)          Tcl Library Procedures
  5.  
  6.  
  7.  
  8. _________________________________________________________________
  9.  
  10. NAME
  11.      Tcl_InitHashTable, Tcl_DeleteHashTable, Tcl_CreateHashEntry,
  12.      Tcl_DeleteHashEntry, Tcl_FindHashEntry, Tcl_GetHashValue,
  13.      Tcl_SetHashValue, Tcl_GetHashKey, Tcl_FirstHashEntry,
  14.      Tcl_NextHashEntry, Tcl_HashStats - procedures to manage hash
  15.      tables
  16.  
  17. SYNOPSIS
  18.      #include <tcl.h>
  19.  
  20.      Tcl_InitHashTable(_t_a_b_l_e_P_t_r, _k_e_y_T_y_p_e)
  21.  
  22.      Tcl_DeleteHashTable(_t_a_b_l_e_P_t_r)
  23.  
  24.      Tcl_HashEntry *
  25.      Tcl_CreateHashEntry(_t_a_b_l_e_P_t_r, _k_e_y, _n_e_w_P_t_r)
  26.  
  27.      Tcl_DeleteHashEntry(_e_n_t_r_y_P_t_r)
  28.  
  29.      Tcl_HashEntry *
  30.      Tcl_FindHashEntry(_t_a_b_l_e_P_t_r, _k_e_y)
  31.  
  32.      ClientData
  33.      Tcl_GetHashValue(_e_n_t_r_y_P_t_r)
  34.  
  35.      Tcl_SetHashValue(_e_n_t_r_y_P_t_r, _v_a_l_u_e)
  36.  
  37.      char *
  38.      Tcl_GetHashKey(_t_a_b_l_e_P_t_r, _e_n_t_r_y_P_t_r)
  39.  
  40.      Tcl_HashEntry *
  41.      Tcl_FirstHashEntry(_t_a_b_l_e_P_t_r, _s_e_a_r_c_h_P_t_r)
  42.  
  43.      Tcl_HashEntry *
  44.      Tcl_NextHashEntry(_s_e_a_r_c_h_P_t_r)
  45.  
  46.      char *
  47.      Tcl_HashStats(_t_a_b_l_e_P_t_r)
  48.  
  49. ARGUMENTS
  50.      Tcl_HashTable    *_t_a_b_l_e_P_t_r    (in)      Address of hash
  51.                                              table structure (for
  52.                                              all procedures but
  53.                                              Tcl_InitHashTable,
  54.                                              this must have been
  55.                                              initialized by pre-
  56.                                              vious call to
  57.                                              Tcl_InitHashTable).
  58.  
  59.      int              _k_e_y_T_y_p_e      (in)      Kind of keys to use
  60.  
  61.  
  62.  
  63. Tcl                                                             1
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. Tcl_Hash(3)          Tcl Library Procedures
  71.  
  72.  
  73.  
  74.                                              for new hash table.
  75.                                              Must be either
  76.                                              TCL_STRING_KEYS,
  77.                                              TCL_ONE_WORD_KEYS,
  78.                                              or an integer value
  79.                                              greater than 1.
  80.  
  81.      char             *_k_e_y         (in)      Key to use for probe
  82.                                              into table.  Exact
  83.                                              form depends on _k_e_y_-
  84.                                              _T_y_p_e used to create
  85.                                              table.
  86.  
  87.      int              *_n_e_w_P_t_r      (out)     The word at *_n_e_w_P_t_r
  88.                                              is set to 1 if a new
  89.                                              entry was created
  90.                                              and 0 if there was
  91.                                              already an entry for
  92.                                              _k_e_y.
  93.  
  94.      Tcl_HashEntry    *_e_n_t_r_y_P_t_r    (in)      Pointer to hash
  95.                                              table entry.
  96.  
  97.      ClientData       _v_a_l_u_e        (in)      New value to assign
  98.                                              to hash table entry.
  99.                                              Need not have type
  100.                                              ClientData, but must
  101.                                              fit in same space as
  102.                                              ClientData.
  103.  
  104.      Tcl_HashSearch   *_s_e_a_r_c_h_P_t_r   (in)      Pointer to record to
  105.                                              use to keep track of
  106.                                              progress in
  107.                                              enumerating all the
  108.                                              entries in a hash
  109.                                              table.
  110. _________________________________________________________________
  111.  
  112.  
  113. DESCRIPTION
  114.      A hash table consists of zero or more entries, each consist-
  115.      ing of a key and a value.  Given the key for an entry, the
  116.      hashing routines can very quickly locate the entry, and
  117.      hence its value.  There may be at most one entry in a hash
  118.      table with a particular key, but many entries may have the
  119.      same value.  Keys can take one of three forms:  strings,
  120.      one-word values, or integer arrays.  All of the keys in a
  121.      given table have the same form, which is specified when the
  122.      table is initialized.
  123.  
  124.      The value of a hash table entry can be anything that fits in
  125.      the same space as a ``char *'' pointer.  Values for hash
  126.  
  127.  
  128.  
  129. Tcl                                                             2
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. Tcl_Hash(3)          Tcl Library Procedures
  137.  
  138.  
  139.  
  140.      table entries are managed entirely by clients, not by the
  141.      hash module itself.  Typically each entry's value is a
  142.      pointer to a data structure managed by client code.
  143.  
  144.      Hash tables grow gracefully as the number of entries
  145.      increases, so that there are always less than three entries
  146.      per hash bucket, on average.  This allows for fast lookups
  147.      regardless of the number of entries in a table.
  148.  
  149.      Tcl_InitHashTable initializes a structure that describes a
  150.      new hash table.  The space for the structure is provided by
  151.      the caller, not by the hash module.  The value of _k_e_y_T_y_p_e
  152.      indicates what kinds of keys will be used for all entries in
  153.      the table.  _K_e_y_T_y_p_e must have one of the following values:
  154.  
  155.      TCL_STRING_KEYS          Keys are null-terminated ASCII
  156.                               strings.  They are passed to hash-
  157.                               ing routines using the address of
  158.                               the first character of the string.
  159.  
  160.      TCL_ONE_WORD_KEYS        Keys are single-word values;  they
  161.                               are passed to hashing routines and
  162.                               stored in hash table entries as
  163.                               ``char *'' values.  The pointer
  164.                               value is the key;  it need not (and
  165.                               usually doesn't) actually point to
  166.                               a string.
  167.  
  168.      _o_t_h_e_r                    If _k_e_y_T_y_p_e is not TCL_STRING_KEYS
  169.                               or TCL_ONE_WORD_KEYS, then it must
  170.                               be an integer value greater than 1.
  171.                               In this case the keys will be
  172.                               arrays of ``int'' values, where
  173.                               _k_e_y_T_y_p_e gives the number of ints in
  174.                               each key.  This allows structures
  175.                               to be used as keys.  All keys must
  176.                               have the same size.  Array keys are
  177.                               passed into hashing functions using
  178.                               the address of the first int in the
  179.                               array.
  180.  
  181.      Tcl_DeleteHashTable deletes all of the entries in a hash
  182.      table and frees up the memory associated with the table's
  183.      bucket array and entries.  It does not free the actual table
  184.      structure (pointed to by _t_a_b_l_e_P_t_r), since that memory is
  185.      assumed to be managed by the client.  Tcl_DeleteHashTable
  186.      also does not free or otherwise manipulate the values of the
  187.      hash table entries.  If the entry values point to
  188.      dynamically-allocated memory, then it is the client's
  189.      responsibility to free these structures before deleting the
  190.      table.
  191.  
  192.  
  193.  
  194.  
  195. Tcl                                                             3
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. Tcl_Hash(3)          Tcl Library Procedures
  203.  
  204.  
  205.  
  206.      Tcl_CreateHashEntry locates the entry corresponding to a
  207.      particular key, creating a new entry in the table if there
  208.      wasn't already one with the given key.  If an entry already
  209.      existed with the given key then *_n_e_w_P_t_r is set to zero.  If
  210.      a new entry was created, then *_n_e_w_P_t_r is set to a non-zero
  211.      value and the value of the new entry will be set to zero.
  212.      The return value from Tcl_CreateHashEntry is a pointer to
  213.      the entry, which may be used to retrieve and modify the
  214.      entry's value or to delete the entry from the table.
  215.  
  216.      Tcl_DeleteHashEntry will remove an existing entry from a
  217.      table.  The memory associated with the entry itself will be
  218.      freed, but the client is responsible for any cleanup associ-
  219.      ated with the entry's value, such as freeing a structure
  220.      that it points to.
  221.  
  222.      Tcl_FindHashEntry is similar to Tcl_CreateHashEntry except
  223.      that it doesn't create a new entry if the key doesn't exist;
  224.      instead, it returns NULL as result.
  225.  
  226.      Tcl_GetHashValue and Tcl_SetHashValue are used to read and
  227.      write an entry's value, respectively.  Values are stored and
  228.      retrieved as type ``ClientData'', which is large enough to
  229.      hold a pointer value.  On almost all machines this is large
  230.      enough to hold an integer value too.
  231.  
  232.      Tcl_GetHashKey returns the key for a given hash table entry,
  233.      either as a pointer to a string, a one-word (``char *'')
  234.      key, or as a pointer to the first word of an array of
  235.      integers, depending on the _k_e_y_T_y_p_e used to create a hash
  236.      table.  In all cases Tcl_GetHashKey returns a result with
  237.      type ``char *''.  When the key is a string or array, the
  238.      result of Tcl_GetHashKey points to information in the table
  239.      entry;  this information will remain valid until the entry
  240.      is deleted or its table is deleted.
  241.  
  242.      Tcl_FirstHashEntry and Tcl_NextHashEntry may be used to scan
  243.      all of the entries in a hash table.  A structure of type
  244.      ``Tcl_HashSearch'', provided by the client, is used to keep
  245.      track of progress through the table.  Tcl_FirstHashEntry
  246.      initializes the search record and returns the first entry in
  247.      the table (or NULL if the table is empty).  Each susequent
  248.      call to Tcl_NextHashEntry returns the next entry in the
  249.      table or NULL if the end of the table has been reached.  A
  250.      call to Tcl_FirstHashEntry followed by calls to
  251.      Tcl_NextHashEntry will return each of the entries in the
  252.      table exactly once, in an arbitrary order.  It is unadvis-
  253.      able to modify the structure of the table, e.g.  by creating
  254.      or deleting entries, while the search is in progress.
  255.  
  256.      Tcl_HashStats returns a dynamically-allocated string with
  257.      overall information about a hash table, such as the number
  258.  
  259.  
  260.  
  261. Tcl                                                             4
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268. Tcl_Hash(3)          Tcl Library Procedures
  269.  
  270.  
  271.  
  272.      of entries it contains, the number of buckets in its hash
  273.      array, and the utilization of the buckets.  It is the
  274.      caller's responsibility to free the result string by passing
  275.      it to free.
  276.  
  277.      The header file tcl.h defines the actual data structures
  278.      used to implement hash tables.  This is necessary so that
  279.      clients can allocate Tcl_HashTable structures and so that
  280.      macros can be used to read and write the values of entries.
  281.      However, users of the hashing routines should never refer
  282.      directly to any of the fields of any of the hash-related
  283.      data structures; use the procedures and macros defined here.
  284.  
  285.  
  286. KEYWORDS
  287.      hash table, key, lookup, search, value
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327. Tcl                                                             5
  328.  
  329.  
  330.  
  331.